package JavaShengSai;

import java.util.Scanner;

/**
 * 9. 斐波那契数列最大公约数
 * https://www.lanqiao.cn/problems/1554/learning/?page=1&first_category_id=1&tags=2020,%E7%9C%81%E8%B5%9B&tag_relation=intersection&sort=pass_rate&asc=0
 */
public class Main15 {
    public static void main1(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        // 两个斐波那契数的最大公约数等于以这两个数的索引的最大公约数为索引的斐波那契数
        // 那么计算两个数的最大公约数
        int a = 2020;
        int b = 520;
        int k = gcb(a,b);
        long ret = fib(k);
        System.out.println(ret);
        scan.close();
    }

    public static int gcb(int a,int b) {
        if(a % b == 0) {
            return b;
        }
        return gcb(b,a % b);
    }

    public static long fib(int k) {
        if(k <= 2) {
            return 1;
        }
        long x = 1L;
        long y = 1L;
        long z = 0;
        for(int i = 3;i <= k;i++) {
            z = x + y;
            x = y;
            y = z;
        }
        return z;
    }
}
